#include "util.h"
#include "common_sort.h"

/*
冒泡排序递归算法
O(n)=O(n^2)

*/

void RecursiveBubbleSort::sort(std::vector<int>& vec, size_t sz) {
	// base case
	if (sz <= 1) {
		return;
	}

	// move largest to end
	for (int i = 0; i < int(sz - 1); ++i) {
		if (vec[i] > vec[i + 1]) {
			util::swap(vec, i, i + 1);
		}
	}

	// recur
	sort(vec, sz - 1);
}

